
Lecture 4: Datatypes and Pattern Matching

* Announcements

1) Read Hickey, Harrison, Harper, Paulson !!

* Tuples

(val1, val2, ..., valN)

n-tuple is a value of a PRODUCT TYPE

typ1 * typ2 * ... * typN

val pair : int * int = (2, 3)
val triple : int * float * string = (2, 2.0, "2")
val quadruple: int * int * float * float = (2,3,2.0,3.0)
val pair of pairs: (int * int) * (float * float) = ((2,3),(2.0,3.0))

NESTING MATTERS

(2,3,2.0,3.0) /= ((2,3),(2.0,3.0))

** Unit

() : unit

void = unit

** No 1-tuples

** Tuple expression

(exp1, exp2, ..., expN) --> (val1, val2, ..., valN) 

val pair : int * int = (1+1, 5-2)

evaluated left to right

** Tuple patterns

BIND-BY-VALUE

let var : typ = exp 

1) Check exp : typ
2) exp --> val
3) Bind val to var




v : (int * string) * (real * char)

let ((_ , _), (f:float, _)) = v

let ((i:int, s:string), (f:float, c:char)) = v

let (is: int*string, fc: float*char) = v

The general form of a value binding is

let pat = exp,

where pat is a pattern and exp is an expression. 

P ::= x | (P, ..., P) | _

* Case Analysis 

** Clausal function definitions

function pat1 -> exp1
       | pat2 -> exp2  
       | ...
       | patN -> expN
 
ORDER MATTERS!

val recip : int -> int =
  fn 0 => 0 
   | n:int => 1 div n

match exp with
  pat1 -> exp1
  ...
  patN -> expN 

is short for

(function 
  pat1 -> exp1
  ...
  patN -> expN) exp

** Boolean conditionals 

fun not true = false
  | not false = true

if exp then e1 else e2 

is short for

match exp with
 true -> e1
 false -> e2

short for

(fn true -> e1 | false -> e2) exp

b1 && b2 
b1 || b2 

is short for

if b1 then b2 else false
if b1 then true else b2

CALL-BY-VALUE IS NOT VIOLATED!!!

** Exaustiveness and Redundancy

*** Exhaustiveness

Exhaustiveness checks that a MATCH covers its domain: every value
matches one of the clauses.

let rec length = function
  | x :: xs -> 1 + length xs

*** Redundancy 

Redundancy checks that no clause is SUBSUMED by a clause preceeding
it. ALWAYS A MISTAKE!

let rec length = function
  | nil -> 0
  | x :: xs -> 1 + length xs
